package subject_set.top101;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/11/01 18:04
 **/
public class BM24 {
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public class Solution {
        List<Integer> list = new ArrayList<>();
        public int[] inorderTraversal (TreeNode root) {
            inOrder(root);
            return list.stream().mapToInt(Integer::intValue).toArray();
        }
        private void inOrder(TreeNode root){
            if(root == null) return;
            inOrder(root.left);
            list.add(root.val);
            inOrder(root.right);
        }
    }

    public class Solution2 {
        public int[] inorderTraversal (TreeNode root) {
            if(root == null) return new int[0];
            List<Integer> list = new LinkedList<>();
            Deque<TreeNode> s = new LinkedList<>();
            while(!s.isEmpty() || root != null){
                while(root != null){
                    s.push(root);
                    root = root.left;
                }
                root = s.pop();
                list.add(root.val);
                root = root.right;
            }
            return list.stream().mapToInt(Integer::intValue).toArray();
        }
    }
}